home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / General Tools / Headers / LowUnionFind.h < prev    next >
Text File  |  1999-07-13  |  969b  |  44 lines
  1. #ifndef LowUnionFind_H
  2. #define LowUnionFind_H
  3.  
  4.  
  5. #include "nodeClass.h"
  6. #include "XLongList.h"
  7.  
  8. class SubTree : public nodeClass, public XLongList {
  9.  
  10. };
  11.  
  12.  
  13. /* 
  14. "Low" in contrast to HighUnionFind in that running time for Union() is O( N ), so 
  15. performace will drop as the number of nodes starts to get very high.
  16. */
  17.  
  18. class LowUnionFind {
  19.  
  20.     public:
  21.                                 LowUnionFind( long inNumVerticies );
  22.                                 ~LowUnionFind();
  23.                                     
  24.         //     Note: O( N )
  25.         void                    AddEdge( long inA, long inB );
  26.         
  27.         //    Returns access to the largest union/subtree in this graph. NULL is returned if there's
  28.         //  no verticies in this graph.
  29.          const XLongList*         LargestPile()                    { return mLargest;            }
  30.          
  31.          
  32.          //    Removes the vertex from all given piles.
  33.          void                    RemoveVertex( long inA );
  34.          
  35.          
  36.      protected:
  37.          XLongList*                mAdj;
  38.          long                    mNumVerticies;
  39.          XLongList*                mLargest;                        // Always pts to the largest node/group/pile
  40.          
  41.          XLongList*                FindLargestPile();
  42. };
  43.  
  44. #endif